﻿
namespace Leetcode.N0699;

public class Solution
{
    public IList<int> FallingSquares(int[][] positions)
    {
        IList<int> heights = new List<int>(positions.Length);

        for (int i = 0; i < positions.Length; i++)
        {
            var preHeight = 0;
            var cur = positions[i];
            var curLeft = cur[0];
            var curRight = cur[0] + cur[1] - 1;

            for (int j = 0; j < i; j++)
            {
                var pre = positions[j];
                var preLeft = pre[0];
                var preRight = pre[0] + pre[1] - 1;

                if (preRight < curLeft || preLeft > curRight)
                {
                    continue;
                }
                preHeight = Math.Max(preHeight, heights[j]);
            }

            heights.Add(positions[i][1] + preHeight);
        }

        for (int i = 1; i < heights.Count; i++)
        {
            heights[i] = Math.Max(heights[i], heights[i - 1]);
        }

        return heights;
    }
}